package leetcode_题库;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/30 9:46 星期二
 */
public class _235_二叉搜索树的最近公共祖先 {

    /**
     * 一个评论
     * > 2022/08/30 10:06:12
     * 解答成功:
     * 	执行耗时:8 ms,击败了34.59% 的Java用户
     * 	内存消耗:42.6 MB,击败了22.92% 的Java用户
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (p.val == root.val) {
            //恰好是树的根，返回
            return p;
        }
        if (q.val == root.val) {
            //恰好是树的根，返回
            return q;
        }

        if (p.val > root.val && q.val > root.val) {
            //都在右边，往右找
            return lowestCommonAncestor(root.right, p, q);
        } else if (p.val < root.val && q.val < root.val) {
            //都在左边，往左找
            return lowestCommonAncestor(root.left, p, q);
        } else {
            //一左一右，他就是最小祖先，可能隔着n辈
            return root;
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
